package Demo01;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Heap {
    public int[] elements;
    //堆当中有效的数据个数
    public int usedSize;
    public Heap() {
        elements = new int[20];
    }

    /**
     * 初始化数组
     */
    public void initArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            elements[i] = arr[i];
            usedSize++;
        }
    }

    /**
     * 创建大根堆
     */
    public void createHeap() {
        for (int i = (usedSize-2)/2; i >= 0 ; i--) {
            adjustDown(i,usedSize);
        }
    }

    /**
     * 向下调整
     * @param parent
     * @param len
     */
    private void adjustDown(int parent, int len) {
        //孩子结点的下标初始化为左孩子的结点的下标
        int child = parent*2 +1;
        //要交换至少你要存在左孩子才能进行交换
        //交换之后,child这个变量代表要交换的那个孩子的下标
        //如果存在左右孩子的话,就比较哪个孩子的值大
        //如果只存在左孩子的话,那么没得选,只能是左孩子下标
        //因为是完全二叉树,所以,存在右孩子必然存在左孩子
        //但是存在左孩子不一定存在右孩子
        while(child<len) {
            //保证右孩子存在,不然可能会导致数组越界
            //右孩子存在且比左孩子大,则要更新child变量
            //child始终是左右孩子最大的那个下标
            if(child+1<len&&
              elements[child]<elements[child+1]) {
                child++;
            }
            //左右孩子最大值大于父结点的值,数值进行交换
            //父结点,孩子结点进行更新,继续向下进行调整
            if(elements[child]>elements[parent]) {
                swap(parent,child);
                parent = child;
                child = parent*2+1;
            }else {
                //如果孩子下标合法,但是父结点比他们最大值还大
                //跳出即可,因为下面的子树本来就调整完了,下面
                //子树的最大值肯定小于父结点的值,那么父结点
                //的值都小于父结点的父亲的值的话,下面没必要进行
                //调整了
                break;
            }
        }
    }
    //判断是否满
    private boolean isFull() {
        return usedSize==elements.length;
    }
    //扩容
    private void enLarger() {
        elements = Arrays.copyOf(elements,elements.length*2);
    }
    private void swap(int parent,int child) {
        int tmp = elements[parent];
        elements[parent] = elements[child];
        elements[child] = tmp;
    }

    /**
     * 对于大根堆来说,如果新的数据比父结点的值小,那么就没必要进行向上调整,
     * 因为父结点的父结点的值一定比父结点大,新的数据比父结点都小,所以一定比
     * 父结点的父结点的值小,但是如果新的数据比父结点的值大,就要交换,新的数据在左结点
     * 或者右节点都只需要和父结点比较,因为即便新数据在右节点,父结点的左节点一定比
     * 父结点小,所以只考虑和父结点的数据进行比较大小即可
     * @param val
     */
    public void insertHeap(int val) {
        if(isFull()) {
            elements = Arrays.copyOf(elements,elements.length*2);
        }
        usedSize++;
        int child = usedSize-1;
        int parent = (child-1)/2;
        elements[child] = val;
        while (child!=0) {
            if(elements[parent]<elements[child]) {
                swap(parent,child);
                child = parent;
                parent = (child-1)/2;
            }else {
                break;
            }
        }
    }

    /**
     * 删除操作
     */
    private boolean empty() {
        return usedSize==0;
    }
    public int pop() {
        //判断是否为空
        if(empty()) {
            //建议自定义异常,此处返回-1
            return -1;
        }
        /*删除优先级最高的根,先让他和最后一个结点互换
         *再让根结点的值进行向下调整
         */
        int rootVal = elements[0];
        usedSize--;
        swap(usedSize,0);
        adjustDown(0,usedSize);
        return rootVal;
    }

    public void heapSort() {
        int end = usedSize-1;
        while (end!=0) {
            swap(0,end);
            adjustDown(0,end--);
        }
    }
}



